package week_03;

import java.util.ArrayList;
import java.util.Deque;
import java.util.LinkedList;
import java.util.List;

public class LevelOrder_429 {

    public List<List<Integer>> levelOrder(Node root) {
        List<List<Integer>> ans = new ArrayList<>();
        if(root==null) return ans;
        Deque<Item> deque = new LinkedList<>();

        deque.add(new Item(root, 0));
        while (!deque.isEmpty()) {
            Item item = deque.getFirst();

            if (item == null) break;
            // 处理当前节点结果进入正确的答案层
            Node cur = item.node;
            int depth = item.depth;
            deque.removeFirst();
            if (ans.size() < depth + 1) {
                ans.add(new ArrayList<>());
            }
            ans.get(depth).add(cur.val);
            for (int i = 0; i < cur.children.size(); i++) {
                deque.add(new Item(cur.children.get(i), depth + 1));
            }
        }
        return ans;
    }

    public class Item {
        public Node node;
        public int depth;

        public Item(Node node, int depth) {
            this.node = node;
            this.depth = depth;
        }
    }
}
